/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adp1;

import java.util.TreeSet;
import java.util.SortedSet;
import java.util.Collection;
import java.util.Set;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import static adp1.Permutations.*;

/**
 *
 * @author panos
 * @author oliver
 */
public class PermutationImageList implements Permutation {

	/*
	 * 
	*	Variables
	*
	*/
	
	
    private List<Integer> imageList;
    
    
    
    
    
    
	/*
	 * 
	*	Creators
	*
	*/
    
    // Constructor for list
    private PermutationImageList(List<Integer> imageList) {
        this.imageList = imageList;
    }

    // Constructor for cycle list with knwon size
    private PermutationImageList(Collection<List<Integer>> cycles, int size) {
        this.imageList = calculateImage(cycles, size);
    }

    /**
     * Create a new permutation
     * 
     * @param imageList a n-size list of integer [a1, ..., an]
     * @return a new permutation object from symmetric group S(n) where \u03c3(i)=ai for all 1\u2264i\u2264n
     * @throws IllegalArgumentException if \u03c3(i)=\u03c3(j) for i\u2260j or if not 1\u2264\u03c3(i)\u2264n for all 1<\u2264i\u2264n
     * @throws NullPointerException if the argument is null
     * 
     */
    static PermutationImageList valueOf(List<Integer> imageList) throws NullPointerException, IllegalArgumentException {
        if (imageList == null) {
            throw new NullPointerException();
        } else if (!checkPreconditionList(imageList, imageList.size())) {
            throw new IllegalArgumentException();
        }
        return new PermutationImageList(imageList);
    }

    // Factory method for cycle list
    static PermutationImageList valueOf(Collection<List<Integer>> cycles) throws IllegalArgumentException {
        List<Integer> temporaryList = calculateTemporaryListFromCycles(cycles);
        if (!checkPreconditionList(temporaryList, temporaryList.size())) {
            throw new IllegalArgumentException();
        }
        return new PermutationImageList(cycles, temporaryList.size());
    }

    // Factory method for cycle list with known size -> allowing missing fixed points
    static PermutationImageList valueOf(Collection<List<Integer>> cycles, int size) throws IllegalArgumentException {
        List<Integer> temporaryList = calculateTemporaryListFromCycles(cycles);
        if (!checkPreconditionList(temporaryList, size)) {
            throw new IllegalArgumentException();
        }
        return new PermutationImageList(cycles, size);
    }

    
    
    
    
    /*
    * 
    *	Accessors
    *
    */
    
    // Get cycle of i of permutation
    @Override
	public List<Integer> cycle(int i) throws IllegalArgumentException {
	    List<List<Integer>> cycles = calculateCycles();
	    if (i < 1 || i > cycles.size()) {
	        throw new IllegalArgumentException();
	    }
	    return cycles.get(i - 1);
	}

    // Get permutation as list
	@Override
    public List<Integer> image() {
        return imageList;
    }

	// Get permutation as set of cycles
    @Override
    public Set<List<Integer>> allCycles() {
        return new HashSet<List<Integer>>(calculateCycles());
    }

    // Get value of permutation image at i
    @Override
    public int sigma(int i) throws IllegalArgumentException {
        if (i < 1 || i > this.size()) {
            throw new IllegalArgumentException();
        }
        return image().get(i - 1);
    }

    // Size of the permuation aka n of Sn
    @Override
    public int size() {
        return image().size();
    }

    // Fixed Points of Permutation
    @Override
    public Set<Integer> fixedPoints() {
        Set<Integer> fixedPoints = new HashSet<Integer>();
        for (int i = 1; i <= this.size(); i++) {
            if (i == sigma(i)) {
                fixedPoints.add(i);
            }
        }
        return fixedPoints;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Permutation)) {
            return false;
        }
        return (this.image().equals(((Permutation) o).image()));
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 59 * hash + (this.imageList != null ? this.imageList.hashCode() : 0);
        hash = 59 * hash + this.size();
        return hash;
    }

    @Override
    public String toImageNotationString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        sb.append(sigma(1));
        for (int i = 2; i <= this.size(); i++) {
            sb.append(" ");
            sb.append(sigma(i));
        }
        sb.append("]");
        return sb.toString();
    }

    @Override
    public String toCycleNotationString() {
        List<List<Integer>> cycles = calculateCycles();
        StringBuilder sb = new StringBuilder();
        for (List<Integer> cycle : cycles) {
            sb.append("(");
            sb.append(cycle.get(0));
            for (int i = 1; i < cycle.size(); i++) {
                sb.append(" ");
                sb.append(cycle.get(i));
            }
            sb.append(")");
        }
        return sb.toString();
    }

    @Override
    public String toString() {
        return toImageNotationString();
    }

    
    
    /*
     * 
    *	Producers
    *
    */
    
    // Get inverse of permutation
	@Override
	public Permutation inverse() {
	    List<Integer> inverseImage = new ArrayList<Integer>();
	    for (int i = 1; i <= this.size(); i++) {
	        inverseImage.add(imageList.indexOf(i) + 1);
	    }
	    return createPermutation(inverseImage);
	}

	// Compose this permuation with permutation p
	@Override
	public Permutation compose(Permutation p) throws NullPointerException, IllegalArgumentException {
	    if (p == null) {
	        throw new NullPointerException();
	    }
	    if (this.size() != p.size()) {
	        throw new IllegalArgumentException();
	    }
	    List<Integer> compositionImage = new ArrayList<Integer>();
	    for (int i = 1; i <= this.size(); i++) {
	        compositionImage.add(p.sigma(this.sigma(i)));
	    }
	    return createPermutation(compositionImage);
	}

	
	
	
	
	/*
	 * 
	*	Helper methods
	*
	*/
	
	
	// Calulate list of cycles from stored image list
	private List<List<Integer>> calculateCycles() {
	    List<List<Integer>> cycles = new ArrayList<List<Integer>>();
	    SortedSet<Integer> done = createSetNn(size());
	    int firstElement = 1;
	    while (!done.isEmpty()) {
	        firstElement = done.first();
	        List<Integer> cycle = new ArrayList<Integer>();
	        int nextElement = firstElement;
	        do {
	            cycle.add(nextElement);
	            done.remove(nextElement);
	            nextElement = sigma(nextElement);
	        } while (nextElement != firstElement);
	        cycles.add(cycle);
	    }
	    return cycles;
	}

	// Calculate image list from cycle list with known size
	private List<Integer> calculateImage(Collection<List<Integer>> cycles, int size) {
	    List<Integer> list = new ArrayList<Integer>();
	    for (int i = 0; i < size; i++) {
	        list.add(i + 1);
	    }
	    for (List<Integer> cycle : cycles) {
	        int element = cycle.get(0);
	        int image;
	        for (int i = 0; i < cycle.size() - 1; i++) {
	            image = cycle.get(i + 1);
	            list.set(element - 1, image);
	            element = image;
	        }
	        image = cycle.get(0);
	        list.set(element - 1, image);
	    }
	    return list;
	}

	// Calculate flat list from cycle list
	private static List<Integer> calculateTemporaryListFromCycles(Collection<List<Integer>> cycles) throws RuntimeException {
	    List<Integer> list = new ArrayList<Integer>();
	    Set<Integer> set = new HashSet<Integer>();
	    for (List<Integer> l : cycles) {
	        if (l.isEmpty()) {
	            throw new RuntimeException();
	        }
	        list.addAll(l);
	        set.addAll(l);
	    }
	    if (list.size() != set.size()) {
	        throw new RuntimeException();
	    }
	    return list;
	}

	// Check if there are any duplicates in list
	private static boolean checkForDuplicatesInList(List<Integer> list) {
	    boolean result = true;
	    if (list.size() != (new HashSet<Integer>(list)).size()) {
	        result = false;
	    }
	    return result;
	}

	// Check if list size and values of the elements are correct
	private static boolean checkForElementsOutOfRange(List<Integer> list, int size) {
	    boolean result = true;
	    for (int i : list) {
	        if (i < 1 || i > size) {
	            result = false;
	        }
	    }
	    return result;
	}

	// Check precondition of a list
	private static boolean checkPreconditionList(List<Integer> list, int size) {
	    return checkForDuplicatesInList(list) && checkForElementsOutOfRange(list, size);
	}

	// Create a sorted set of integers 1,2,..,n
	private SortedSet<Integer> createSetNn(int n) {
	    SortedSet<Integer> set = new TreeSet<Integer>();
	    for (int i = 1; i <= n; i++) {
	        set.add(i);
	    }
	    return set;
	}
}
